Как посчитать сложность алгоритма в Big O?

Как посчитать сложность алгоритма в Big O?

Алгоритмические задачки — редкость на русскоязычных собеседованиях. Но там, где их спрашивают, просят оценить сложность в Big O-нотации. Сложность алгоритма оценивают или по расходу памяти или по времени исполнения. Память обычно никого не интересует: когда говорят о сложности — подразумевают время исполнения в худшем случае.

Сложность в Big O на пальцах Предположим, у вас есть функция, которая принимает массив чисел linear([]). Вы передаёте в такую функцию массив с 1 элементом linear([1]) и замеряете время исполнения. Пусть будет ровно 1 секунда. Теперь вы передаёте 2 элемента в ту же функцию linear([1, 2]) и снова замеряете время. Получилось 2 секунды. Выходит, что обработка каждого элемента занимает 1 секунду. Если будет 10 элементов — алгоритм выполнится за 10 секунд. Выходит, это линейная сложность или O(n), где n — количество элементов.

Big O ничего не говорит о конкретном времени исполнения алгоритма, но показывает, как это время будет расти вместе с увеличением количества входных данных.

O(1) — константная сложность Время исполнения такого алгоритма будет одинаковым при любом количестве входных данных. Например, обращение к элементу массива по индексу: не важно, миллиард у вас элементов или всего 1. Самая популярная сложность O(1) — это обращение к хеш-таблице (объектам, Map и Set в JavaScript). [1s, 1s, 1s, 1s, ..., 1s]

O(log n) — логарифмическая сложность Единственный реальный пример — это Бинарный поиск: рекурсивное деление отсортированного массива пополам, до тех пор, пока элемент не окажется слева или справа. [1s, 1s, 1.6s, 2s, 2.3s, ...]

O(n) — линейная сложность Пример O(n) — это полный перебор массива элементов. Не забывайте так же о стандартных, встроенных методах, которые внутри перебирают массивы: поиск элемента в массиве, поиск символа в строке. [1s, 2s, 3s, 4s, 5s, ...]

O(n^2) — квадратичная сложность Что произойдёт, если вложить один цикл в другой? Мы переберём каждый элемент с каждым или n * n = n^2. Почти все виды сортировок дают O(n^2). [1s, 4s, 9s, 16s, 25s, ...]

Как считать? Помните, что Big O рассматривает сложность в худшем случае. А значит, бОльшая сложность поглощает меньшую. Теперь откройте ваш алгоритм и попробуйте найти: - Перебор входного массива — это O(n) - Десять переборов массива — O(10n) = O(n) - Перебор массива, который не связан со входными данными — O(1) - Перебор массива внутри перебора — O(n * n) = O(n^2) - Сортировка массива — в худшем случае O(n^2) - Сортировка массива и его перебор: O(n^2 + n) = O(n^2)

☁️ Строки — тоже массивы: для них справедливы те же принципы. ☁️ В большинстве задачек вам нужно сократить сложность от цикла в цикле O(n^2) до одного цикла O(n). Попробуйте использовать переменные вне цикла и хэш-таблицы. ☁️ Погуглите, какая сложность в каждом стандартном методе, который используете. ☁️ Чтобы быстрее научиться видеть сложность — тренируйтесь оценивать сложность решений, которые публикуют другие читатели.

⚡️ Предлагайте темы и подписывайте друзей на канал!

const matrix = [
  ['F', 'A', 'C', 'E'],
  ['O', 'B', 'O', 'P'],
  ['N', 'A', 'R', 'B'],
  ['E', 'A', 'N', 'D']
]

check(matrix, 'FACE') // true check(matrix, 'CORN') // true check(matrix, 'AND') // true check(matrix, 'FONT') // false

Размещайте ответы на JS Bin и скидывайте ссылку в чат канала. Смотрите, спрашивайте и комментируйте чужие решения.